Modified Virtual Grid Difference for Discretizing the Laplace-Beltrami Operator on Point Clouds

摘要

We propose a new and simple discretization, named the Modified Virtual GridDifference (MVGD), for numerical approximation of the Laplace-Beltrami (LB)operator on manifolds sampled by point clouds. The key observation is that boththe manifold and a function defined on it can both be parametrized in a localCartesian coordinate system and approximated using least squares. Based on theabove observation, we first introduce a local virtual grid with a scale adaptedto the sampling density centered at each point. Then we propose a modifiedfinite difference scheme on the virtual grid to discretize the LB operator.Instead of using the local least squares values on all virtual grid points likethe typical finite difference method, we use the function value explicitly atthe grid located at the center (coincided with the data point). The newdiscretization provides more diagonal dominance to the resulting linear systemand improves its conditioning. We show that the linear system can be robustly,efficiently and accurately solved by existing fast solver such as the AlgebraicMultigrid (AMG) method. We will present numerical tests and comparison withother exiting methods to demonstrate the effectiveness and the performance ofthe proposed approach.